import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.sortedSquares(new int[]{-4, -1, 0, 3, 10})));
        System.out.println(Arrays.toString(s.sortedSquares(new int[]{-7, -3, 2, 3, 11})));
    }
}


class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        int i = 0, j = nums.length - 1;
        int k = nums.length - 1;
        while(i <= j){
            if(Math.abs(nums[i]) > Math.abs(nums[j])){
                ans[k--] = nums[i] * nums[i];
                i++;
            }
            else{
                ans[k--] = nums[j] * nums[j];
                j--;
            }
        }
        return ans;
    }
}


class Solution1 {
    public int[] sortedSquares(int[] nums) {
        int minAbsIdx = findAbsMin(nums);
        int[] ans = new int[nums.length];
        int i = minAbsIdx, j = minAbsIdx + 1;
        for(int k = 0; k < nums.length; k++){
            if(i < 0 || j < nums.length && Math.abs(nums[i]) > Math.abs(nums[j])){
                ans[k] = nums[j] * nums[j];
                j++;
            }
            else {
                ans[k] = nums[i] * nums[i];
                i--;
            }
        }
        return ans;
    }

    int findAbsMin(int[] nums){
        int l = 0, h = nums.length - 1;
        int minIdx = 0;
        while(l <= h){
            int mid = (l + h) >> 1;
            if(nums[mid] == 0){
                return mid;
            }
            minIdx = Math.abs(nums[mid]) < Math.abs(nums[minIdx]) ? mid : minIdx;
            if(nums[mid] > 0){
                h = mid - 1;
            }
            if(nums[mid] < 0){
                l = mid + 1;
            }
        }
        return minIdx;
    }
}